{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Lucky Numbers in a Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: luckyNumbers "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵中的幸运数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m * n</code> 的矩阵，矩阵中的数字 <strong>各不相同</strong> 。请你按 <strong>任意</strong> 顺序返回矩阵中的所有幸运数。</p>\n",
    "\n",
    "<p><strong>幸运数</strong> 是指矩阵中满足同时下列两个条件的元素：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>在同一行的所有元素中最小</li>\n",
    "\t<li>在同一列的所有元素中最大</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[3,7,8],[9,11,13],[15,16,17]]\n",
    "<strong>输出：</strong>[15]\n",
    "<strong>解释：</strong>15 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]\n",
    "<strong>输出：</strong>[12]\n",
    "<strong>解释：</strong>12 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[7,8],[1,2]]\n",
    "<strong>输出：</strong>[7]\n",
    "<strong>解释：</strong>7是唯一的幸运数字，因为它是行中的最小值，列中的最大值。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n, m &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;matrix[i][j]&nbsp;&lt;= 10^5</code></li>\n",
    "\t<li>矩阵中的所有元素都是不同的</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lucky-numbers-in-a-matrix](https://leetcode.cn/problems/lucky-numbers-in-a-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lucky-numbers-in-a-matrix](https://leetcode.cn/problems/lucky-numbers-in-a-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,7,8],[9,11,13],[15,16,17]]', '[[1,10,4,2],[9,3,8,7],[15,16,17,12]]', '[[7,8],[1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "        rows_min = []\n",
    "        cols_max = []\n",
    "        res=[]\n",
    "        for i in range(len(matrix)):\n",
    "            tmp = [x for x in matrix[i]]\n",
    "            tmp.sort()\n",
    "            rows_min.append(tmp[0])\n",
    "        for j in range(len(matrix[0])):\n",
    "            tmp = [matrix[i][j] for i in range(len(matrix))]\n",
    "            tmp.sort()\n",
    "            cols_max.append(tmp[-1])   \n",
    "        for i in rows_min:\n",
    "            if i in cols_max:\n",
    "                res.append(i)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "        return list(set(min(row) for row in matrix) & set(max(col)  for col in zip(*matrix)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "        ''' solution 1. 40ms 13.8mb '''\n",
    "        col_mins = [-1]*len(matrix)\n",
    "        col_indices = [-1]*len(matrix)\n",
    "        row_maxs = [float('inf')]*len(matrix[0])\n",
    "\n",
    "        for i in range(0, len(matrix)):\n",
    "            min_val = float('inf')\n",
    "            for j in range(0, len(matrix[i])):\n",
    "                if matrix[i][j]< min_val:\n",
    "                    min_val = matrix[i][j]\n",
    "                    col_mins[i] = min_val\n",
    "                    col_indices[i] = j\n",
    "\n",
    "        res = []\n",
    "        # 计算每列最大的\n",
    "\n",
    "        for idx, (minv, cidx)  in enumerate(zip(col_mins, col_indices)):\n",
    "            if row_maxs[cidx] == float('inf'):\n",
    "                row_maxs[cidx] = max([matrix[j][cidx] for j in range(0, len(matrix))]) \n",
    "            if row_maxs[cidx] == minv:\n",
    "                res.append(minv)\n",
    "\n",
    "        return res\n",
    "                 \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "        ''' solution 1. 40ms 13.8mb '''\n",
    "        col_mins = [-1]*len(matrix)\n",
    "        col_indices = [-1]*len(matrix)\n",
    "        row_maxs = [float('inf')]*len(matrix[0])\n",
    "\n",
    "        for i in range(0, len(matrix)):\n",
    "            min_val = float('inf')\n",
    "            for j in range(0, len(matrix[i])):\n",
    "                if matrix[i][j]< min_val:\n",
    "                    min_val = matrix[i][j]\n",
    "                    col_mins[i] = min_val\n",
    "                    col_indices[i] = j\n",
    "\n",
    "        res = []\n",
    "        # 计算每列最大的\n",
    "\n",
    "        for idx, (minv, cidx)  in enumerate(zip(col_mins, col_indices)):\n",
    "            if row_maxs[cidx] == float('inf'):\n",
    "                row_maxs[cidx] = max([matrix[j][cidx] for j in range(0, len(matrix))]) \n",
    "            if row_maxs[cidx] == minv:\n",
    "                res.append(minv)\n",
    "\n",
    "        return res\n",
    "                 \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "        ''' solution 1. 40ms 13.8mb '''\n",
    "        col_mins = [-1]*len(matrix)\n",
    "        col_indices = [-1]*len(matrix)\n",
    "        row_maxs = [float('inf')]*len(matrix[0])\n",
    "\n",
    "        for i in range(0, len(matrix)):\n",
    "            min_val = float('inf')\n",
    "            for j in range(0, len(matrix[i])):\n",
    "                if matrix[i][j]< min_val:\n",
    "                    min_val = matrix[i][j]\n",
    "                    col_mins[i] = min_val\n",
    "                    col_indices[i] = j\n",
    "\n",
    "        res = []\n",
    "        # 计算每列最大的\n",
    "\n",
    "        for idx, (minv, cidx)  in enumerate(zip(col_mins, col_indices)):\n",
    "            if row_maxs[cidx] == float('inf'):\n",
    "                row_maxs[cidx] = max([matrix[j][cidx] for j in range(0, len(matrix))]) \n",
    "            if row_maxs[cidx] == minv:\n",
    "                res.append(minv)\n",
    "\n",
    "        return res\n",
    "                 \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        minrow = {}\n",
    "        output = []\n",
    "        for i in range(m):\n",
    "            minrow[min(matrix[i])] = 1\n",
    "        for j in range(n):\n",
    "            maxi = max([i[j] for i in matrix])\n",
    "            if maxi in minrow: output.append(maxi)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "        mr,mc=set(),set()\n",
    "        for row in matrix:\n",
    "            \n",
    "            mr.add(min(row))\n",
    "        for col in zip(*matrix):\n",
    "            \n",
    "            mc.add(max(col))\n",
    "        \n",
    "        \n",
    "        return[x for x in mr if x in mc]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "\n",
    "        row = []\n",
    "        for r in matrix:\n",
    "            row.append(min(r))\n",
    "\n",
    "        col = []\n",
    "        for c in range(len(matrix[0])):\n",
    "            num = -math.inf\n",
    "            for r in range(len(matrix)):\n",
    "                num= max(matrix[r][c], num)\n",
    "            col.append(num)\n",
    "        ans = []\n",
    "        for r in row:\n",
    "            for c in col:\n",
    "                if r == c:\n",
    "                    ans.append(r)\n",
    "                    break\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "        w=[min(i) for i in matrix]\n",
    "        h=[max(i) for i in list(zip(*matrix))]\n",
    "        return list(set(w)&set(h))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "        cols = list(zip(*matrix))\n",
    "        # print(cols)\n",
    "        rowMins = []\n",
    "        colMaxs = []\n",
    "        for row in matrix:\n",
    "            rowMins.append(min(row))\n",
    "        for col in cols:\n",
    "            colMaxs.append(max(col))\n",
    "        res = []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                item = matrix[i][j]\n",
    "                if item == rowMins[i] and item == colMaxs[j]:\n",
    "                    res.append(item)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "      mins = {min(rows) for rows in matrix}\n",
    "      maxes = {max(columns) for columns in zip(*matrix)}\n",
    "      return list (mins & maxes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "        h,w=len(matrix),len(matrix[0])\n",
    "        max_cols={max([matrix[y][x] for y in range(h)]) for x in range(w)}\n",
    "        min_rows={min([matrix[y][x] for x in range(w)]) for y in range(h)}\n",
    "        result=list(max_cols&min_rows)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:\n",
    "        for i in range(len(matrix)):\n",
    "            a = matrix[i]\n",
    "            ans = min(a)\n",
    "            for j in range(len(matrix)):\n",
    "                if ans < matrix[j][matrix[i].index(ans)]:\n",
    "                    break\n",
    "            else:           \n",
    "                return [ans]\n",
    "                break\n",
    "        else:\n",
    "            return []\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
